﻿using System;
using System.Collections.Generic;
using System.Text;

namespace 二叉排序树___链式存储
{
    class BSTree
    {
        BSNode root = null;
        public void Add(int item)
        {
            BSNode newNode = new BSNode(item);
            if (root == null)
            {
                root = newNode;
            }
            else
            {
                BSNode temp = root;
                while (true)
                {
                    if (item > temp.Data)
                    {
                        if (temp.RightChild == null)
                        {
                            temp.RightChild = newNode;
                            newNode.Parent = temp;
                            break;
                        }
                        else
                        {
                            temp = temp.RightChild;
                        }
                    }
                    else
                    {
                        if (temp.LeftChild == null)
                        {
                            temp.LeftChild = newNode;
                            newNode.Parent = temp;
                            break;
                        }
                        else
                        {
                            temp = temp.LeftChild;
                        }
                    }
                }
            }
        }

        public void MiddleTraversal()
        {
            MiddleTraversal(root);
        }
        public void MiddleTraversal(BSNode node)
        {
            if (node == null) return;

            MiddleTraversal(node.LeftChild);
            Console.Write(node.Data + " ");
            MiddleTraversal(node.RightChild);
        }

        public bool Find(int item)
        {
             return Find(item, root);
        }
        private bool Find(int item,BSNode node)
        {
            if (node == null) return false;
            if(node.Data == item)
            {
                return true;
            }
            else
            {
                if (item > node.Data)
                {
                    return Find(item, node.RightChild);
                }
                else
                {
                    return Find(item, node.LeftChild);
                }
            }
        }


        public bool Delete(int item)
        {
            BSNode temp = root;
            while (true)
            {
                if (temp == null) return false;
                if (temp.Data == item)
                {
                    Delete(temp);
                    return true;
                }
                if (item > temp.Data)
                    temp = temp.RightChild;
                else
                    temp = temp.LeftChild;
            }
        }
        private void Delete(BSNode node)
        {
            if(node.LeftChild == null && node.RightChild == null)
            {
                if(node.Parent == null)
                {
                    root = null;
                }
                else if (node.Parent.LeftChild == node)
                {
                    node.Parent.LeftChild = null;
                }
                else if(node.Parent.RightChild == node)
                {
                    node.Parent.RightChild = null;
                }
                return;
            }

            if(node.LeftChild == null && node.RightChild != null)
            {
                BSNode rc = node.RightChild;

                node.Data = rc.Data;
                node.RightChild = rc.RightChild;
                node.LeftChild = rc.LeftChild;

                rc.LeftChild.Parent = node;
                rc.RightChild.Parent = node;
                return;
            }

            if (node.LeftChild != null && node.RightChild == null)
            {
                BSNode lc = node.LeftChild;
                node.Data = lc.Data;
                node.LeftChild = lc.LeftChild;
                node.RightChild = lc.RightChild;

                lc.LeftChild.Parent = node;
                lc.RightChild.Parent = node;
                return;
            }

            BSNode temp = node.RightChild;
            while (true)
            {
                if (temp.LeftChild != null)
                {
                    temp = temp.LeftChild;
                }
                else
                {
                    break;
                }
            }
            node.Data = temp.Data;
            Delete(temp);
            

        }
    }
}
